package sort;

import java.util.Random;

/**
 * @Auther: MFM
 * @Date: 2022/3/19 - 03 - 19 - 19:39
 * @version: 1.0
 */

public class InsertionSort {
    //简单插入排序
    public void simpleInsertionSort(int[] arr) {
        if (arr == null) {
            return;
        }

        //从索引1 开始 一直到数组末尾
        for (int i = 1; i < arr.length; i++) {
            //提供变量 保存临时数据
            int e = arr[i];
            //从i往前找符合条件的数
            int index = i;

            //若不符合条件 先复制数组 当都没有arr[index - 1]<e 的数说明 原arr[i]最小 放到最前面 此时index=0 arr[index] = e
            while (index > 0 && arr[index - 1] > e) {
                arr[index] = arr[index - 1];
                index--;
            }

            //如果index没有移动说明 arr[i] 为最大的数最大的数直接放在排好序的数组中不用再赋值
            if (index != i) {
                arr[index] = e;
            }

        }
    }

    //希尔排序
    public void shellSort(int[] arr) {
        if (arr==null){
            return;
        }

        //增量分组 一直到1为止 数组长度奇偶不影响排序
        for (int i = arr.length/2; i > 0; i/=2) {
            //每组都做插入排序
            for (int j = i; j < arr.length; j++) {

                int e = arr[j];

                int index = j;

                while (index - i >= 0 && e < arr[index - i]){
                    arr[index] = arr[index - i];
                    index-=i;
                }

                if (index != j){
                    arr[index] = e;
                }
            }

        }
    }

    public static void main(String[] args) {
        /*
         * 测试结果
         * 1000000 排序所用时间为
         * 简单插入排序 90s+
         * 希尔排序 200ms
         * */
        int[] arr = new int[1000000];
        Random r = new Random();


        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }

        long start = System.currentTimeMillis();

        new InsertionSort().shellSort(arr);

        long end = System.currentTimeMillis();

        System.out.println(end - start);
//        int[] arr = {15,5,2,7,12,6,1,4,3,9,8};
//
//        new InsertionSort().shellSort(arr);
//
//        for (int a : arr
//        ) {
//            System.out.print(a + " ");
//        }

    }
}
